Classic learning theory suggests that proper regularization is the key to good generalization and robustness. In classification, current training schemes only target the complexity of the classifier itself, which can be misleading and ineffective. Instead, we advocate directly measuring the complexity of the decision boundary. Existing literature is limited in this area with few well-established definitions of boundary complexity. As a proof of concept, we start by analyzing ReLU neural networks, whose boundary complexity can be conveniently characterized by the number of affine pieces. With the help of tropical geometry, we develop a novel method that can explicitly count the exact number of boundary pieces, and as a by-product, the exact number of total affine pieces. Numerical experiments are conducted and distinctive properties of our boundary complexity are uncovered. First, the boundary piece count appears largely independent of other measures, e.g., total piece count, and $l_2$ norm of weights, during the training process. Second, the boundary piece count is negatively correlated with robustness, where popular robust training techniques, e.g., adversarial training or random noise injection, are found to reduce the number of boundary pieces.

Several current bounds on the maximal number of affine regions of a ReLU feed-forward neural network are special cases of the framework [1] which relies on layer-wise activation histogram bounds. We analyze and partially solve a problem in algebraic topology the solution of which would fully exploit this framework. Our partial solution already induces slightly tighter bounds and suggests insight in how parameter initialization methods can affect the number of regions. Furthermore, we extend the framework to allow the composition of subnetwork instead of layer-wise activation histogram bounds to reduce the number of required compositions which negatively affect the tightness of the resulting bound.

R { } is equipped with the standard maximum and sum operations, respectively. It has been used to represent various nonlinear processes, in areas such as scheduling and synchronization [2], [6], [9], geometry [22], control theory and optimization [1], [4], morphological image and signal analysis [15], [24], [28], and machine learning [7], [8], [29], [32], [33]. Max-plus algebra is obtained from the conventional linear algebra if we replace addition with maximum and multiplication with addition, as an extension of the max-plus semiring to multiple dimensions. Hence, many of the aforementioned nonlinear processes enjoy some linear-like properties when described in terms of the max-plus algebra. In this paper we are interested in sparse max-plus representations, i.e. vectors which consist of as many uninformative () elements as possible.